package leetcode.day_2021_3_1_2022_3_7;

import java.util.Arrays;

/**
 * 37. 解数独
 * https://leetcode-cn.com/problems/sudoku-solver/
 */
public class LeetCode0037 {
    static int[][] row = new int[9][10];
    static int[][] col = new int[9][10];
    static int[][] box = new int[9][10];

    public static void solveSudoku(char[][] board) {
        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                if (board[i][j] == '.') continue;;
                int curNum = board[i][j] - '0';
                row[i][curNum] = 1;
                col[j][curNum] = 1;
                box[j/3+(i/3)*3][curNum] = 1;
            }
        }
        fillRowColBox(board, 0, 0);
    }

    public static boolean isValid(char[][] board, int i, int j, int num) {
        if (row[i][num]==0 && col[j][num]==0 && box[j/3+(i/3)*3][num]==0) return true;
        return false;
    }

    public static void fillRowColBox(char[][] board, int row, int col) {
        if (row==8 && col==8) return;
        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                if (board[i][j] == '.') {
                    for (int k=1; k<=9; k++) {
                        if (!isValid(board, i, j, k)) {
                            continue;
                        }
                        board[i][j] = (char) (k + '0');
                        fillRowColBox(board, i, j);
                        board[i][j] = '.';
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        char[][] arr = {{'5','3','.','.','7','.','.','.','.'},
                {'6','.','.','1','9','5','.','.','.'},
                {'.','9','8','.','.','.','.','6','.'},
                {'8','.','.','.','6','.','.','.','3'},
                {'4','.','.','8','.','3','.','.','1'},
                {'7','.','.','.','2','.','.','.','6'},
                {'.','6','.','.','.','.','2','8','.'},
                {'.','.','.','4','1','9','.','.','5'},
                {'.','.','.','.','8','.','.','7','9'}};
        solveSudoku(arr);
        System.out.println(Arrays.toString(arr));
    }
}
